package lt639
/*
91 题

639. 解码方法 II
一条包含字母 A-Z 的消息通过以下的方式进行了编码：

'A' -> 1
'B' -> 2
...
'Z' -> 26
要 解码 一条已编码的消息，所有的数字都必须分组，然后按原来的编码方案反向映射回字母（可能存在多种方式）。
例如，"11106" 可以映射为：

"AAJF" 对应分组 (1 1 10 6)
"KJF" 对应分组 (11 10 6)
注意，像 (1 11 06) 这样的分组是无效的，因为 "06" 不可以映射为 'F' ，因为 "6" 与 "06" 不同。

除了 上面描述的数字字母映射方案，编码消息中可能包含 '*' 字符，可以表示从 '1' 到 '9' 的任一数字（不包括 '0'）。例如，编码字符串 "1*" 可以表示 "11"、"12"、"13"、"14"、"15"、"16"、"17"、"18" 或 "19" 中的任意一条消息。对 "1*" 进行解码，相当于解码该字符串可以表示的任何编码消息。

给你一个字符串 s ，由数字和 '*' 字符组成，返回 解码 该字符串的方法 数目 。

由于答案数目可能非常大，返回对 109 + 7 取余 的结果。

*/
func check1digit(ch byte) int {
    if ch == '*' {      //对应【1，9】
        return 9
    }
    if ch == '0' {			//无法被编码
        return 0
    }
    return 1
}

func check2digits(c0, c1 byte) int {   //使用两个字符的情况
    if c0 == '*' && c1 == '*' {   //s[i-1]  s[i]均为*
        return 15  //[11,19][21,26]  15种
    }
    if c0 == '*' {   //仅有s[i-1]为*   
        if c1 <= '6' {    //s[i]∈[0,6]  s[i-1]可选1，2
            return 2
        }
        return 1   //否则只能选择1
    }
    if c1 == '*' {    //仅有s[i]=*，
        if c0 == '1' {	//s[i-1]=1   则s[1]可以为1-9
            return 9
        }
        if c0 == '2' {  //对应21-26
            return 6
        }
        return 0
    }
    if c0 != '0' && (c0-'0')*10+(c1-'0') <= 26 { //均不为*   只有s[i-1]不为0，且数字小于等于26
        return 1
    }
    return 0
}

func numDecodings(s string) int {
    const mod int = 1e9 + 7
    a, b, c := 0, 1, 0
    for i := range s {
        c = b * check1digit(s[i]) % mod
        if i > 0 {
            c = (c + a*check2digits(s[i-1], s[i])) % mod
        }
        a, b = b, c
    }
    return c
}
